/*
 * @lc app=leetcode.cn id=79 lang=cpp
 *
 * [79] 单词搜索
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<bool>> visited;
    /**
     * @brief
     *
     * @param target 目标字符串
     * @param x 当前位置x
     * @param y 当前位置y
     * @param pos 当前需要进行匹配的字符的位置
     * @return true
     * @return false
     */
    bool bfs(vector<vector<char>> &board, const string &target, int x, int y, int pos)
    {
        if (pos == target.size())
            return true;
        if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size())
            if (!visited[x][y] && board[x][y] == target[pos])
            {
                visited[x][y] = true;
                bool flag = false;
                flag |= bfs(board, target, x + 1, y, pos + 1);
                if (!flag)
                    flag |= bfs(board, target, x - 1, y, pos + 1);
                if (!flag)
                    flag |= bfs(board, target, x, y + 1, pos + 1);
                if (!flag)
                    flag |= bfs(board, target, x, y - 1, pos + 1);
                visited[x][y] = false;
                return flag;
            }
        return false;
    }
    bool exist(vector<vector<char>> &board, string word)
    {
        visited = vector<vector<bool>>(board.size(), vector<bool>(board[0].size(), 0));
        bool flag = false;
        for(int i = 0; i < board.size(); i++)
        {
            for(int j = 0; j < board[0].size(); j++)
            {
                if(bfs(board, word, i, j, 0))
                {
                    return true;
                }
            }
        }
        return false;
    }
};
// int main()
// {
//     vector<vector<char>> board = {
//         {'A', 'B', 'C', 'E'},
//         {'S', 'F', 'C', 'S'},
//         {'A', 'D', 'E', 'E'}};
    
//     Solution().exist(board, "SEE");
//     return 0;
// }
// @lc code=end
